package com.hyper_yang.algorithmRecord.June;

import java.util.ArrayDeque;
import java.util.Deque;

// 2025.06.06 使用机器人打印字典序最小的字符串
public class LeetCode_2434 {
    /*
    给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
    删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
    删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
    请你返回纸上能写出的字典序最小的字符串。
     */

    /* ❌ incorrect 8/64 这只能针对简单问题，考虑不全面 */
//    public String robotWithString(String s) {
//        StringBuilder res = new StringBuilder();
//        // 维护一个单调递增栈
//        Deque<Character> stack = new ArrayDeque<>();
//        for (char c : s.toCharArray()) {
//            if (stack.isEmpty() || c >= stack.peek()) {
//                stack.push(c);
//            } else {
//                res.append(c);
//                while (!stack.isEmpty()) {
//                    res.append(stack.pop());
//                }
//            }
//        }
//        while (!stack.isEmpty())
//            res.append(stack.pop());
//        return res.toString();
//    }

    // 改进: 栈 + 后续最小值 √ pass
    public String robotWithString1(String s) {
        int n = s.length();
        char[] min = new char[n + 1];
        min[n] = Character.MAX_VALUE; // 哨兵
        // 初始化 s 后缀最小值数组
        for (int i = n - 1; i >= 0; i--) {
            min[i] = (char) Math.min(s.charAt(i), min[i + 1]);
        }
        StringBuilder res = new StringBuilder();
        // 维护一个单调递增栈
        Deque<Character> stack = new ArrayDeque<>();
        // 需要用索引访问 后续最小值数组 改用 for
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            stack.push(c);
            // 栈顶元素比所有剩余元素还要小 对于 i判断, i+1及之后元素
            while (!stack.isEmpty() && stack.peek() <= min[i + 1])
                res.append(stack.pop());
        }
        while (!stack.isEmpty())
            res.append(stack.pop());
        return res.toString();
    }

    // 参考学习: leetcode 官方题解 【贪心 ＋ 栈】
    public String robotWithString(String s) {
        // 初始化 cnt数组，记录 s中字符种类数量
        int[] cnt = new int[26];
        for (char c : s.toCharArray())
            cnt[c - 'a']++;
        StringBuilder res = new StringBuilder();
        ArrayDeque<Character> stack = new ArrayDeque<>();
        char min = 'a';
        for (char c : s.toCharArray()) {
            stack.push(c);
            cnt[c - 'a']--; // 对于 c之后的判断，要排除 c来看
            while (min != 'z' && cnt[min - 'a'] == 0) {
                min++;
            }
            while (!stack.isEmpty() && stack.peek() <= min) {
                res.append(stack.pop());
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
        LeetCode_2434 solution = new LeetCode_2434();
        System.out.println(solution.robotWithString("zza")); // azz
        System.out.println(solution.robotWithString("bac")); // abc
        System.out.println(solution.robotWithString("bdda")); // addb
        System.out.println(solution.robotWithString("bydizfve")); // bdevfziy
    }
}
